#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include"reverse_iterator.h"

namespace my_list
{
	//节点部分
	template<class T>
	struct list_node
	{
		list_node<T>* _prev, * _next;
		T _data;

		list_node(const T& value = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _data(value)
		{}
	};

	//迭代器部分  T Ref=T& Ptr=T*
	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node; //节点指针
		typedef __list_iterator<T,Ref,Ptr> self; //迭代器对象

		node* _node;

		__list_iterator(node* n)
			:_node(n)
		{}

		//返回__list_iterator对象引用
		self& operator++()//前置++
		{
			_node = _node->_next;
			return *this;
		}

		//返回__list_iterator对象
		self operator++(int)//后置++
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()//前置--
		{
			_node = _node->_prev;
			return *this;
		}

		self operator--(int)//后置--
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		//迭代器比较
		bool operator!=(const self& n) const { return _node != n._node; }
		bool operator==(const self& n) const { return _node == n._node; }

		//返回T&——解引用访问数据
		Ref operator*()  { return _node->_data;}

		//返回T*——自定义类型需要->访问成员(其_data可能是一个自定义类型)
		Ptr operator->() { return &_node->_data; }

	};


	//链表部分
	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		typedef __list_iterator<T,T&,T*> iterator;
		typedef __list_iterator<T,const T&,const T*> const_iterator;
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<iterator,const T&,const T*> const_reverse_iterator;

		typedef T& reference;
		typedef const T& const_reference;

		//库中是通过以下两种构造函数实现功能的
		//list() { Empty_Init(); }

		//list(int n, const_reference value = T())
		//{
		//	Empty_Init();
		//	while (n--) { push_back(value); }
		//}

		list(int n = 0, const_reference value = T())
		{
			Empty_Init();
			while (n--) { push_back(value); }
		}

		template <class InputIterator>//迭代器区间构造
		list(InputIterator first, InputIterator last)
		{
			Empty_Init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			Empty_Init();
			list<T> tmp(l.begin(), l.end());
			swap(tmp);
		}

		list<T>& operator=(list<T> l)
		{
			swap(l);
			return *this;
		}

		//交换
		void swap(list<T>& l) { std::swap(_head, l._head); }

		//清空
		void clear()
		{
			if(empty()) return; //如果为空则不执行
			iterator it = begin();
			while (it != end()) { erase(it++); }
		}

		//调整
		void resize(size_t n, const_reference val = T())
		{
			if (n > size())
				while (size() < n) push_back(val);
		}

		~list()
		{
			if(!empty())
				clear();

			delete _head;
			_head = nullptr;
		}

		//void push_front(const_reference val) //头插
		//{
		//	node* newnode = new node(val); //新节点
		//	node* frontnode = _head->_next; //当前第一个有效节点

		//	//更新链接关系
		//	_head->_next = newnode; //头节点指向新节点
		//	newnode->_prev = _head; //新节点的前驱指向头节点
		//	newnode->_next = frontnode; //新节点指向原第一个有效节点
		//	frontnode->_prev = newnode; //向原第一个有效节点的前驱更新为新节点
		//	//insert(begin(), val);
		//}

		//void push_back(const_reference val) //尾插
		//{
		//	node* newnode = new node(val); //新节点
		//	node* backnode = _head->_prev; //尾节点

		//	//更新链接关系
		//	_head->_prev = newnode;
		//	newnode->_next = _head;
		//	newnode->_prev = backnode;
		//	backnode->_next = newnode;

		//	//insert(end(), val);
		//}

		//void pop_front() //头删
		//{
		//	assert(!empty()); //检查是否为空链表
		//	node* frontnode = _head->_next; //当前第一个有效节点
		//	node* frontnext = frontnode->_next; //记录第二个有效节点

		//	//让_head与第二个有效节点链接
		//	_head->_next = frontnext;
		//	frontnext->_prev = _head;

		//	//删除原第一个有效节点
		//	delete frontnode;
		//	frontnode = nullptr;
		//	//erase(begin());
		//}

		//void pop_back() //尾删
		//{
		//	assert(!empty()); //检查是否为空链表
		//	node* backnode = _head->_prev; //尾节点
		//	node* backprev = backnode->_prev; //尾节点前驱

		//	//更新链接更新-剥离尾节点
		//	_head->_prev = backprev;
		//	backprev->_next = _head;

		//	//删除尾节点
		//	delete backnode;
		//	backnode = nullptr;

		//	//erase(--end());
		//}

		//头插
		void push_front(const_reference val) { insert(begin(), val); }

		//尾插
		void push_back(const_reference val) { insert(end(), val); }

		//头删
		void pop_front() { erase(begin()); }

		//尾删
		void pop_back() { erase(--end()); }


		iterator insert(iterator pos, const_reference val)
		{
			assert(pos._node); //确保节点非空
			node* newnode = new node(val); //创建新节点
			node* posprev = pos._node->_prev; //获取pos节点的前驱

			//更新链接关系 - 将新节点链入pos节点与pos前驱节点之间
			newnode->_next = pos._node;
			newnode->_prev = posprev;
			posprev->_next = newnode;
			pos._node->_prev = newnode;
			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			//链表非空&确保节点非空&不为头节点_head
			assert(!empty() && pos._node && pos._node != _head); 

			node* posprev = pos._node->_prev; //pos的下一个节点
			node* posnext = pos._node->_next; //pos的上一个节点
			node* freenode = pos._node;

			//链接posprev和posnext 剥离 pos 节点
			posprev->_next = posnext;
			posnext->_prev = posprev;

			delete freenode; //释放pos节点
			return iterator(posnext); //返回pos节点的下一个节点的迭代器
		}

		//正向迭代器
		iterator begin() { return iterator(_head->_next); } //普通迭代器
		iterator end() { return iterator(_head); }

		const_iterator begin() const { return const_iterator(_head->_next); } //const普通迭代器
		const_iterator end() const { return const_iterator(_head); }

		const_iterator cbegin() const { return const_iterator(_head->_next); } //const迭代器
		const_iterator cend() const { return const_iterator(_head); }


		//反向迭代器
		reverse_iterator rbegin() { return reverse_iterator(end()); }
		reverse_iterator rend() { return reverse_iterator(begin()); }

		const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
		const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

		const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
		const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }

		reference front()
		{
			assert(!empty());
			return _head->_next->_data;
		}

		const_reference front() const
		{
			assert(!empty());
			return _head->_next->_data;
		}

		reference back()
		{
			assert(!empty());
			return _head->_prev->_data;
		}

		const_reference back() const
		{
			assert(!empty());
			return _head->_prev->_data;
		}

		size_t size()const
		{
			size_t sz = 0;
			const_iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}

		bool empty()const { return _head->_next == _head; }

	private:
		node* _head;

		void Empty_Init()
		{
			_head = new node;
			_head->_next = _head->_prev = _head;
			_head->_data = T();
		}
	};
}
